package com.hanxiaozhang.no10leetcode.link;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给定头节点，判断链表是否有环
 * <p>
 * 参考：com.hanxiaozhang.link.fastslowpointer.FastSlowPointerTopic#isRingNode(com.hanxiaozhang.link.singlylink.Node)
 * <p>
 * 需要背下来
 * <p>
 * 思路：
 * 1. 设置两个指针slow、fast，从头指针开始，每次分别前进1步、2步。
 * 2. 如存在环，则两者相遇；如不存在环，fast遇到null退出。
 * 拓展：
 * 相遇点（碰撞点）：快慢指针有环时，相遇的点。
 *
 * @author hanxinghua
 * @create 2024/2/1
 * @since 1.0.0
 */
public class No141LinkedListCycle {


    public static void main(String[] args) {

        // 1->2->3 <- 8 <- 7
        //        \->       \ ->
        //         4        6
        //          \->   / ->
        //             5
        Node head1 = new Node(1);
        head1.next = new Node(2);
        Node node3 = new Node(3);
        head1.next.next = node3;
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next.next = new Node(8);
        head1.next.next.next.next.next.next.next.next = node3;

        System.out.println(isRingNode(head1));
    }


    /**
     * 是否有环
     * <p>
     * 设置两个指针slow、fast，从头指针开始，每次分别前进1步、2步。
     * 如存在环，则两者相遇；如不存在环，fast遇到null退出。
     *
     * @param head
     * @return
     */
    private static boolean isRingNode(Node head) {

        if (head == null || head.next == null || head.next.next == null) {
            return false;
        }
        Node slow = head.next;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null) {
            if (slow == fast) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        return false;
    }
}
